package com.xinpan.exercise;

import java.util.ArrayList;

public class SortedListToBST {
	
	   static class ListNode 
	    {
	    	      int val;
	    	      ListNode next;
	    	      ListNode(int x) { val = x; next = null; }
	    }
	    	 
	    	
	    class TreeNode {
	    	      int val;
	    	      TreeNode left;
	    	     TreeNode right;
	    	      TreeNode(int x) { val = x; }
	     }
	
	    public TreeNode sortedListToBST(ListNode head) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        if(head == null)
	            return null;
	            
	        ArrayList<TreeNode> nodeList = new ArrayList<TreeNode>();
	        while(head != null)
	        {
	            nodeList.add(new TreeNode(head.val));
	            head = head.next;
	        }    
	                
	        
	        int last = nodeList.size() - 1;
	        int mid = last/2;
	        TreeNode root = nodeList.get(mid);
	        root.left = createTree(0, mid-1, nodeList);
	        root.right = createTree(mid+1, last, nodeList);
	        
	        return root;
	    }
	    
	    
	    public TreeNode createTree(int s, int e, ArrayList<TreeNode> nodeList)
	    {
	        if(e < s)
	            return null;
	        
	        int mid = (s+e)/2;
	        TreeNode root = nodeList.get(mid);
	        root.left = createTree(s, mid-1, nodeList);
	        root.right = createTree(mid+1, e, nodeList);
	        
	        return root;
	    }
    
    public static void main(String[] args)
    {
    	SortedListToBST slbst = new SortedListToBST();
    	
    	ListNode a = new ListNode(3);
    	ListNode b = new ListNode(5);
    	ListNode c = new ListNode(8);
    	
    	a.next = b;
    	b.next = c;
    	
    	
    	slbst.sortedListToBST(a);
    }
    
 
}


